package threeSum

import ()

func ThreeSum(num []int) [][]int {
	if len(num) < 3 {
		return nil
	}
	num = Sort(num)
	res := make([][]int, 0)
	size := len(num)
	for first := 0; first < size; first++ {
		if first > 0 && num[first] == num[first-1] {
			continue
		}
		third := size - 1
		target := -num[first]

		for second := first + 1; second < size; second++ {
			if second > first+1 && num[second] == num[second-1] {
				continue
			}
			for second < third && num[second]+num[third] > target {
				third--
			}
			if second == third {
				break
			}
			if num[second]+num[third] == target {
				res = append(res, []int{num[first], num[second], num[third]})

			}
		}
	}

	return res

}

func Sort(num []int) []int {
	for i := 0; i < len(num)-1; i++ {
		for j := i + 1; j < len(num); j++ {
			if num[i] > num[j] {
				num[i], num[j] = num[j], num[i]
			}
		}
	}
	return num
}
